\section{Introduction}\label{sec:introduction}

Bitcoin is a decentralized electronic cash system that has become increasingly popular since its introduction in 2008 \cite{nakamoto2008bitcoin}. The base currency, the \emph{bitcoin} or \emph{BTC}, is defined in terms of \emph{transactions}, which are mappings from a sender address to a receiver address, where addresses are simply public keys. All transactions are stored in a public ledger, the \emph{block chain}. Since all transactions are public, user anonymity in Bitcoin relies on pseudonyms. There has been much work on de-anonymizing users in the bitcoin block chain by linking together transactions \cite{fleder2014bitcoin}. If any one of the linked addresses can be mapped to the true identity of a user, then all past and future transactions involving the linked addresses can be attributed to that user, which may not be desirable.

\subsection{Mixing Services} To alleviate this risk of deanonymization, a number of Bitcoin \emph{mixing services}, or \emph{laundries} have arisen. These services allow users to exchange their bitcoins for "clean" bitcoins that are hard to link to their current addresses and identities. To participate in a mixing operation, a user supplies some amount of BTC from an input address, and specifies an output address that they wish these bitcoins to end up in eventually. However, many current designs lack certain features that may be desirable. We now describe properties that we believe an ideal system should offer.
\begin{itemize}
\item \emph{Accountability}. When a user sends funds to the mix, they should be confident that if a theft occurs, they can bring the mix to justice.
\item \emph{Anonymity}. The user should be the only entity that knows the mapping from their input address to their output address. 
\item \emph{Resilience to Misbehaving Users.} The system should not be vulnerable to attacks by a small number of malicious parties that could potentially DoS the exchange \cite{coinjoin},\cite{multiparty}.
\item \emph{Scalability}. The system should efficient enough to be able to scale to accomidate for large anonymity sets.
\item \emph{Incentivization}. There should be a mechanism for the mix to collect mixing fees fairly that will incentivize it to provide the service. Also, the cost for users should be reasonable for the value of the service provided.
\item \emph{Backwards-Compatibility}. The system should be compatible with the current Bitcoin system to allow for practical integration.
\end{itemize}

\subsection{Our Contribution} We assume the reader is familiar with both the Mixcoin and the Bitcoin protocols \cite{nakamoto2008bitcoin}, \cite{bonneau2014mixcoin}. Our contribution consists of adding modifications to the Mixcoin protocol that prevent the mix from learning input/output address pairs. The Mixcoin authors mention that such a scheme could be possible using blinded tokens as described in Chaum's original digital cash scheme \cite{chaum1983blind}. We show that this is indeed possible and present a protocol that achieves this goal. Our system is based on the Mixcoin system and draws many of its ideas from it. The main modifications that we make are the introduction of an append-only public log that is used to keep the mix accountable, and  the utilization of a commutative encryption scheme to hide the mapping between a user's input and output addresses from the mix. 

Our proposed system meets all of the above goals for a mixing service. For accountability, we use a warranty scheme that allows the user to provide evidence against the mix if it misbehaves, similar to \cite{bonneau2014mixcoin}. Anonymity is provided by using Chaum's blinded signature scheme to hide the output addresses of a transaction. The user then connects anonymously to unblind their output address. The system also is resilient to DoS attacks by a single user refusing to sign a joint transaction, as certain schemes are susceptible to \cite{coinjoin}, \cite{multiparty}. This is possible since the mix deals with each user individually, and can exclude users from the exchange on a case-by-case basis. The system is scalable since it does not require any computationally complex encryption as do some other systems \cite{multiparty}. Finally, the system is backwards compatible with Bitcoin, requiring no changes to the current protocol.
